// https://leetcode.cn/problems/longest-palindromic-substring/

/*
给你一个字符串 s，找到 s 中最长的回文子串。
*/
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
	// 暴力法
    string longestPalindrome(string s) {
		int len = s.size();
		if(len == 1) return s;
		int realLeft = 0, realRight = 0;
		for(int i = 0; i < len; i++){
			for(int j = len - 1; j > i; j--){
				if(s[i] != s[j]){
					continue;
				}else{
					if((j - i > realRight - realLeft) && isPalindrome(s, i, j)){
						realRight = j;
						realLeft = i;
						break;
					}
				}
			}
		}
		return s.substr(realLeft, realRight - realLeft + 1);
    }
	
	bool isPalindrome(string s, int left, int right){
		while(left < right){
			if(s[left] == s[right]){
				left++;
				right--;
			}else{
				return false;
			}
		}
		return true;
	}
	
	string longestPalindrome1(string s) {
		string s1 = s;
		reverse(s.begin(), s.end());
		
	}
};

int main(){
	// string s = "abcdefedcba";
	string s = "aacabdkacaa";
	Solution so;
	string a = so.longestPalindrome(s);
	cout << a << endl;
	return 0;
}